package Tree;

public class _437_PathSumIII {
    int count;
    int sum;
    public int pathSum_1(TreeNode root, int sum) {
        this.count = 0;
        this.sum = sum;
        helper(root, 0, false);
        return count;
    }

    public void helper(TreeNode root, int tsum, boolean dupli) {
        if (root == null) return;
        tsum = tsum + root.val;
        if (tsum == sum) {
            count++;
            helper(root.left, tsum, true);
            helper(root.right, tsum, true);
        } else if (tsum != sum) {
            helper(root.left, tsum, true);
            helper(root.right, tsum, true);
        }
        if (dupli) {
            return ;
        }
        helper(root.left, 0, false);
        helper(root.right, 0, false);
    }

    public int pathSum(TreeNode root, int sum) {
        if(root==null) return 0;
        return pathSumFrom(root, sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
    }

    public int pathSumFrom(TreeNode root, int sum) {
        if(root==null) return 0;
        return (root.val == sum ? 1 : 0)
                + pathSumFrom(root.left, sum - root.val) + pathSumFrom(root.right, sum - root.val);
    }
}
